package chapter01.problem05;

import java.util.Stack;

/**
 * 利用一个额外的栈来进行排序
 * @author Administrator
 *
 */
public class SortStackUseStack {

	public static void sortStack(Stack<Integer> stack){
		Stack<Integer> help = new Stack<Integer>();//辅助栈
		while(!stack.isEmpty()){
			Integer top = stack.pop();
			//如果辅助栈的栈顶不空，并且辅助栈的栈顶大于top，则将辅助栈的栈顶弹出并压入stack栈顶
			//否则的话表明辅助栈的元素都小于top。
			while(!help.isEmpty() && help.peek() > top){
				stack.push(help.pop());
			}
			//将top压入辅助栈
			help.push(top);
		}
		//将辅助栈中的元素复制到stack中，辅助栈中按照从大到小的顺序排，则stack的顺序就按照从小到大
		while(!help.isEmpty()){
			stack.push(help.pop());
		}
	}
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(3);
		stack.push(2);
		stack.push(2);
		stack.push(4);
		stack.push(5);
		stack.push(1);
		System.out.println(stack);
		SortStackUseStack.sortStack(stack);
		System.out.println(stack);
	}
}
